import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class GraphSearch
{

    /**
     * Searches the Graph passed in as an AdjcencyList(adjList) to find if a path exists from the start node to the goal node
     * using General Graph Search.
     *
     * Assume the AdjacencyList contains adjacent nodes of each node in the order they should be visited.
     *
     * The structure(struct) passed in is an empty structure may behave as a Stack or Queue and the
     * correspondingly search function should execute DFS(Stack) or BFS(Queue) on the graph.
     *
     * @param start
     * @param struct
     * @param adjList
     * @param goal
     * @return true if path exists false otherwise
     */
    public static <T> boolean search(T start, Structure<T> struct, Map<T, List<T>> adjList, T goal)
    {
        struct.clear();
        List<T> visitedList = new LinkedList<T>();
        struct.add(start);
        while(!struct.isEmpty())
        {
            T current = struct.remove();
            visitedList.add(current);
            if(current.equals(goal))
            {
                return true;
            }

            if(adjList.get(current) != null)
            {
                for(T t : adjList.get(current))
                {
                    if(!visitedList.contains(t))
                    {
                        struct.add(t);
                    }
                }
            }
        }
        return false;
    }

    /**
     * Find the shortest distance between the start node and the goal node in the given a weighted graph
     * in the form of an adjacency list where the edges only have positive weights
     * Return the aforementioned shortest distance if there exists a path between the start and goal,-1
     * otherwise.
     *
     * Assume the AdjacencyList contains adjacent nodes of each node in the order they should be visited.
     * There are no negative edge weights in the graph.
     *
     * @param start
     * @param adjList
     * @param goal
     * @return the shortest distance between the start and the goal no   de
     */
    public static <T> int dsp(T start, Map<T, List<Pair<T, Integer>>> adjList, T goal)
    {
        //System.out.println();
        HashMap<T,Integer> tentativeDistances = new HashMap<T,Integer>();
        List<T> visitedList = new LinkedList<T>(); //make a list of all nodes that have been visited
        LinkedList<T> unvisited = new LinkedList<T>();
        T current = start;
        T next = null;

        tentativeDistances.put(current,0);

        if(current == goal)
        {
            return 0;
        }
        while(!visitedList.contains(current))
        {
            //add all of currents children to the hashmap if they arent there already.
            if(adjList.get(current) != null)
            {
                for(Pair node : adjList.get(current))
                {
                    if(tentativeDistances.get(node.a)== null)
                    {

                        tentativeDistances.put((T)node.a,Integer.MAX_VALUE);

                    }
                }
            }
            if(adjList.get(current) != null)
            {
                int currMin = Integer.MAX_VALUE;
                //for each node of current
                for(Pair node : adjList.get(current))
                {
                    if(!visitedList.contains(node.a)) //if the node is not in visited
                    {
                        int tentativeDistance = (Integer)node.b + tentativeDistances.get(current);
                        if(tentativeDistance<tentativeDistances.get(node.a))
                        {
                            tentativeDistances.remove(node.a);
                            tentativeDistances.put((T)node.a,tentativeDistance);
                            //System.out.println("SET DISTANCE: " + (String)node.a + " "+ tentativeDistance );
                        }

                        if(tentativeDistance<currMin)
                        {
                            currMin = tentativeDistance;

                            next = (T)node.a;
                            //System.out.println("NEXT: " + (String)next);
                        }
                    }
                }
                for(Pair node : adjList.get(current))
                {
                    if(node.a != next && !visitedList.contains(node.a) && !unvisited.contains(node.a))
                    {
                        unvisited.add((T)node.a);
                       // System.out.println("unvisited: "+(String)node.a);

                    }
                }
            }
            visitedList.add(current);
            unvisited.remove(current);
            //System.out.println("Visited: "+ (String) current);

            current = next;
            //System.out.println("current is now : "+ (String)next);

            if(visitedList.contains(current) && !unvisited.isEmpty())
            {
                current = unvisited.remove();
                next = current;
               // System.out.println("new next: "+ (String) current);

            }
            //System.out.println("LOOOP");
            //System.out.println();
        }
        //System.out.println("DONE");
        if(tentativeDistances.get(goal) == null)
        {
            return -1;

        }
        else
        {
            return tentativeDistances.get(goal);
        }
    }

}
